\chapter{Compactness}
\label{ch:compactness}
One of the most important notions of topological spaces is that of \emph{compactness}.
It generalizes the notion of ``closed and bounded'' in Euclidean space
to any topological space
(e.g.\ see \Cref{thm:bzw}).

For metric spaces, there are two equivalent ways of formulating compactness:
\begin{itemize}
	\ii A ``natural'' definition using \emph{sequences}, called sequential compactness.
	\ii A less natural definition using open covers.
\end{itemize}
As I alluded to earlier, sequences in metric spaces are super nice,
but sequences in general topological spaces \emph{suck} (to the point where
I didn't bother to define convergence of general sequences).
So it's the second definition that will be used for general spaces.

\section{Definition of sequential compactness}
\prototype{$[0,1]$ is compact, but $(0,1)$ is not.}
To emphasize, compactness is one of the
\emph{best} possible properties that a metric space can have.
\begin{definition}
	A \vocab{subsequence} of an infinite sequence
	$x_1, x_2, \dots$ is exactly what it sounds like:
	a sequence $x_{i_1}, x_{i_2}, \dots$
	where $i_1 < i_2 < \cdots$ are positive integers.
	Note that the sequence is required to be infinite.
\end{definition}
Another way to think about this is ``selecting infinitely many terms''
or ``deleting some terms'' of the sequence, depending on whether
your glass is half empty or half full.

\begin{definition}
	A metric space $M$ is \vocab{sequentially compact} if
	every sequence has a subsequence which converges.
\end{definition}
This time, let me give some non-examples before the examples.
\begin{example}
	[Non-examples of compact metric spaces]
	\listhack
	\begin{enumerate}[(a)]
		\ii The space $\RR$ is not compact: consider the sequence $1,2,3,4,\dots$.
		Any subsequence explodes, hence $\RR$ cannot possibly be compact.
		\ii More generally, if a space is
		not bounded it cannot be compact.
		(You can prove this if you want.)
		\ii The open interval $(0,1)$ is bounded but not compact:
		consider the sequence $\frac12, \frac13, \frac14, \dots$.
		No subsequence can converge to a point in $(0,1)$ because the sequence ``converges to $0$''.
		\ii More generally, any space which is not complete cannot be compact.
	\end{enumerate}
\end{example}

Now for the examples!
\begin{ques}
	Show that a finite set is compact.
	(Pigeonhole Principle.)
\end{ques}
\begin{example}[Examples of compact spaces]
	Here are some more examples of compact spaces.
	I'll prove they're compact in just a moment;
	for now just convince yourself they are.
	\begin{enumerate}[(a)]
		\ii $[0,1]$ is compact. Convince yourself of this!
		Imagine having a large number of dots in the unit interval\dots
		\ii The surface of a sphere, $S^2 = \left\{ (x,y,z) \mid x^2+y^2+z^2=1 \right\}$ is compact.
		\ii The unit ball $B^2 = \left\{ (x,y) \mid x^2+y^2 \le 1 \right\}$ is compact.
		\ii The \vocab{Hawaiian earring} living in $\RR^2$ is compact:
		it consists of mutually tangent circles of radius $\frac 1n$ for each $n$,
		as in \Cref{fig:hawaiian}.
	\end{enumerate}
\end{example}
\begin{figure}[ht]
	\centering
	\begin{asy}
		size(4cm);
		for (int n=1; n<=15; ++n) draw(CP(dir(0)/n, origin));
		fill(CP(dir(0)/15, origin), black);
	\end{asy}
	\caption{Hawaiian Earring.}
	\label{fig:hawaiian}
\end{figure}

To aid in generating more examples, we remark:
\begin{proposition}[Closed subsets of compacts]
	Closed subsets of sequentially compact sets are compact.
\end{proposition}
\begin{ques}
	Prove this. (It should follow easily from definitions.)
\end{ques}

We need to do a bit more work for these examples, which we do in the next section.

\section{Criteria for compactness}
%Quick note: right now I've only defined compactness for metric spaces.
%In the next section I'll define compactness for general spaces, but
%all the results in this section will still remain true.
%However the proofs become much harder (in particular, \Cref{thm:tychonoff}
%becomes notoriously difficult).
%So you should assume all spaces in this section are metric spaces.

\begin{theorem}
	[Tychonoff's theorem]
	\label{thm:tychonoff}
	If $X$ and $Y$ are compact spaces, then so is $X \times Y$.
\end{theorem}
\begin{proof}
	\Cref{prob:tychonoff}.
\end{proof}

We also have:
\begin{theorem}[The interval is compact]
	\label{thm:interval_compact}
	$[0,1]$ is compact.
\end{theorem}
\begin{proof}
	Killed by \Cref{thm:bzw};
	however, here is a sketch of a direct proof.
	Split $[0,1]$ into $[0,\half] \cup [\half,1]$.
	By Pigeonhole, infinitely many terms of the sequence lie in the left half (say);
	let $x_1$ be the first one and then keep only the terms in the left half after $x_1$.
	Now split $[0, \half]$ into $[0,\frac14] \cup [\frac14,\half]$.
	Again, by Pigeonhole, infinitely many terms fall in some half; pick one of them, call it $x_2$.
	Rinse and repeat.
	In this way we generate a sequence $x_1$, $x_2$, \dots\ which is Cauchy,
	implying that it converges since $[0,1]$ is complete.
\end{proof}

Now we can prove the main theorem about Euclidean space:
in $\RR^n$, compactness is equivalent to being ``closed and bounded''.
\begin{theorem}[Bolzano-Weierstra\ss]
	A subset of $\RR^n$ is compact if and only if it is closed and bounded.
	\label{thm:fakeBW}
\end{theorem}
\begin{ques}
	Why does this imply the spaces in our examples are compact?
\end{ques}
\begin{proof}
	Well, look at a closed and bounded $S \subseteq \RR^n$.
	Since it's bounded, it lives inside some box $[a_1, b_1] \times [a_2, b_2] \times \dots \times [a_n, b_n]$.
	By Tychonoff's theorem, since each $[a_i, b_i]$ is compact the entire box is.
	Since $S$ is a closed subset of this compact box, we're done.
\end{proof}

One really has to work in $\RR^n$ for this to be true!
In other spaces, this criterion can easily fail.
\begin{example}[Closed and bounded but not compact]
	Let $S = \{s_1, s_2, \dots\}$ be any infinite set equipped with the discrete metric.
	Then $S$ is closed (since all convergent sequences are constant sequences)
	and $S$ is bounded (all points are a distance $1$ from each other)
	but it's certainly not compact since the sequence $s_1, s_2, \dots$ doesn't converge.
\end{example}

The Bolzano-Weierstrass theorem, which is \Cref{thm:bzw}, tells you exactly
which sets are compact in metric spaces in a geometric way.

\section{Compactness using open covers}
\prototype{$[0,1]$ is compact.}
There's a second related notion of compactness which I'll now define.
The following definitions might appear very unmotivated, but bear with me.
\begin{definition}
	An \vocab{open cover} of a topological space $X$
	is a collection of open sets $\{U_\alpha\}$
	(possibly infinite or uncountable) which \emph{cover} it:
	every point in $X$ lies in at least one of the $U_\alpha$,
	so that \[ X = \bigcup U_\alpha. \]

	A \vocab{subcover} is exactly what it sounds like:
	it takes only some of the $U_\alpha$,
	while ensuring that $X$ remains covered.
\end{definition}

Some art:
\begin{center}
\begin{asy}
size(12cm);
path blob = (-8,3)..(-10,1)..(-9.4,0)..(-8.2,-3)..(-8,-4)
	..(-2,-4.3)..(2,-4.2)..(8,-4)
	..(8.6,-2)..(8.2,0.5)..(8,3)
	..(4,3.3)..(0,3.1)..(-6,2.9)..cycle;
void open_ball(pair O, real r, pen p) {
	dot(O, p);
	filldraw(CR(O, r), p+opacity(0.1), p+dashed);
}

filldraw(blob, cyan+opacity(0.2), blue+0.7);
open_ball((-7,0.8), 3.5, red);
open_ball((-4.7,-1.2), 4.6, orange);
open_ball((-1.7,-0.3), 3.9, red);
open_ball((1.4,0.9), 2.9, yellow);
open_ball((2.5,-0.9), 3.7, orange);
open_ball((0.4,-3.7), 1.3, yellow);
open_ball((4.3,0.8), 2.7, red);
open_ball((6.3,1.8), 2.4, orange);
open_ball((6.0,-2.4), 4.0, yellow);

label("$X$", (8,3), dir(5), blue);

label(scale(2)*"$X = \bigcup_\alpha U_\alpha$", (0,4), blue);
\end{asy}
\end{center}


\begin{definition}
	A topological space $X$ is \vocab{quasicompact}
	if \emph{every} open cover has a finite subcover.
	It is \vocab{compact} if it is also Hausdorff.
\end{definition}
\begin{remark}
	The ``Hausdorff'' hypothesis that I snuck in
	is a sanity condition which is not worth worrying about unless you're
	working on the algebraic geometry chapters,
	since all the spaces you will deal with are Hausdorff.
	(In fact, some authors don't even bother to include it.)
	For example all metric spaces are Hausdorff
	and thus this condition can be safely ignored
	if you are working with metric spaces.
\end{remark}
What does this mean? Here's an example:
\begin{example}[Example of a finite subcover]
	Suppose we cover the unit square $M = [0,1]^2$ by
	putting an open disk of diameter $1$ centered at every point
	(trimming any overflow).
	This is clearly an open cover because,
	well, every point lies in \emph{many} of the open sets,
	and in particular is the center of one.

	But this is way overkill -- we only need about four
	of these circles to cover the whole square.
	That's what is meant by a ``finite subcover''.
	\begin{center}
		\begin{asy}
			size(4cm);
			draw(shift( (-0.5,-0.5) )*unitsquare, black+1);
			real d = 0.4;
			real r = 0.5;
			draw(CR(dir( 45)*d, r), dotted);
			draw(CR(dir(135)*d, r), dotted);
			draw(CR(dir(225)*d, r), dotted);
			draw(CR(dir(315)*d, r), dotted);
		\end{asy}
	\end{center}
\end{example}

Why do we care?
Because of this:
\begin{theorem}[Sequentially compact $\iff$ compact]
	A metric space $M$ is sequentially compact if and only if it is compact.
	\label{thm:compactness_metric}
\end{theorem}
We defer the proof to the last section.

This gives us the motivation we wanted for our definition.
Sequential compactness was a condition that made sense.
The open-cover definition looked strange,
but it turned out to be equivalent.
But we now prefer it, because we have seen that
whenever possible we want to resort to open-set-only based definitions:
so that e.g.\ they are preserved under homeomorphism.

\begin{example}[An example of non-compactness]
	The space $X = [0,1)$ is not compact in either sense. % chktex 9
	We can already see it is not sequentially compact, because it is not even complete (look at $x_n = 1 - \frac 1n$).
	To see it is not compact under the covering definition, consider the sets
	\[ U_m = \left[0, 1 - \frac{1}{m+1} \right) \] % chktex 9
	for $m = 1, 2, \dots$. Then $X = \bigcup U_i$; hence the $U_i$ are indeed a cover.
	But no finite collection of the $U_i$'s will cover $X$.
\end{example}
\begin{ques}
	Convince yourself that $[0,1]$ \emph{is} compact;
	this is a little less intuitive than it being sequentially compact.
\end{ques}
\begin{abuse}
	Thus, we'll never call a metric space ``sequentially compact'' again
	--- we'll just say ``compact''.
	(Indeed, I kind of already did this in the previous few sections.)
\end{abuse}


\section{Applications of compactness}
Compactness lets us reduce \emph{infinite} open covers to finite ones.
Actually, it lets us do this even if the open covers are \emph{blithely stupid}.
Very often one takes an open cover consisting
of an open neighborhood of $x \in X$ for every single point $x$ in the space;
this is a huge number of open sets,
and yet compactness lets us reduce to a finite set.

To give an example of a typical usage:
\begin{proposition}[Compact $\implies$ totally bounded]
	Let $M$ be compact. Then $M$ is totally bounded.
\end{proposition}
\begin{proof}[Proof using covers]
	For every point $p \in M$, take an $\eps$-neighborhood of $p$, say $U_p$.
	These cover $M$ for the horrendously stupid reason that each point $p$ is
	at the very least covered by its open neighborhood $U_p$.
	Compactness then lets us take a finite subcover.
\end{proof}

Next, an important result about maps between compact spaces.
\begin{theorem}[Images of compacts are compact]
	Let $f \colon X \to Y$ be a continuous function, where $X$ is compact.
	Then the image \[ f\im(X) \subseteq Y \] is compact.
\end{theorem}
\begin{proof}[Proof using covers]
	Take any open cover $\{V_\alpha\}$ in $Y$ of $f\im(X)$.
	By continuity of $f$,
	it pulls back to an open cover $\{U_\alpha\}$ of $X$.
	Thus some finite subcover of this covers $X$.
	The corresponding $V$'s cover $f\im(X)$.
\end{proof}
\begin{ques}
	Give another proof using the sequential definitions
	of continuity and compactness.
	(This is even easier.)
\end{ques}

Some nice corollaries of this:
\begin{corollary}
	[Extreme value theorem]
	Let $X$ be compact and consider a continuous function $f \colon X \to \RR$.
	Then $f$ achieves a \emph{maximum value} at some point,
	i.e.\ there is a point $p \in X$ such that $f(p) \ge f(q)$ for any
	other $q \in X$.
\end{corollary}
\begin{corollary}
	[Intermediate value theorem]
	Consider a continuous function $f \colon [0,1] \to \RR$.
	Then the image of $f$ is of the form $[a,b]$ for some real numbers $a \le b$.
\end{corollary}

\begin{proof}[Sketch of Proof]
	The point is that the image of $f$ is compact in $\RR$,
	and hence closed and bounded.
	You can convince yourself that the closed sets are just unions of closed intervals.
	That implies the extreme value theorem.

	When $X=[0,1]$, the image is also connected,
	so there should only be one closed interval in $f\im([0,1])$.
	Since the image is bounded, we then know it's of the form $[a,b]$.
	(To give a full proof, you would use the so-called \emph{least upper bound}
	property, but that's a little involved for a bedtime story;
	also, I think $\RR$ is boring.)
\end{proof}

\begin{example}
	[$1/x$]
	The compactness hypothesis is really important here.
	Otherwise, consider the function
	\[ (0,1) \to \RR \quad \text{ by } \quad
		x \mapsto \frac 1x. \]
	This function (which you plot as a hyperbola) is not bounded;
	essentially, you can see graphically that the issue
	is we can't extend it to a function on $[0,1]$ because it explodes near $x=0$.
\end{example}

One last application: if $M$ is a compact metric space,
then continuous functions $f \colon M \to N$
are continuous in an especially ``nice'' way:
\begin{definition}
	A function $f \colon M \to N$ of metric spaces
	is called \vocab{uniformly continuous}
	if for any $\eps > 0$, there exists a $\delta > 0$
	(depending only on $\eps$) such that
	whenever $d_M(x,y) < \delta$ we also have $d_N(f(x), f(y)) < \eps$.
\end{definition}
The name means that for $\eps > 0$,
we need a $\delta$ that works for \emph{every point} of $M$.
\begin{example}[Uniform continuity]
	\listhack
	\begin{enumerate}[(a)]
		\ii The functions $\RR$ to $\RR$ of the form
		$x \mapsto ax+b$ are all uniformly continuous,
		since one can always take $\delta = \eps/|a|$ (or $\delta=1$ if $a=0$).
		\ii Actually, it is true that a differentiable function $\RR \to \RR$
		with a bounded derivative is uniformly continuous.
		(The converse is false for the reason that uniformly continuous
		doesn't imply differentiable at all.)
		\ii The function $f \colon \RR \to \RR$ by $x \mapsto x^2$
		is \emph{not} uniformly continuous, since for large $x$,
		tiny $\delta$ changes to $x$ lead to fairly large changes in $x^2$.
		(If you like, you can try to prove this formally now.)

		Think $f(2017.01) - f(2017) > 40$;
		even when $\delta = 0.01$, one can still cause large changes in $f$.

		\ii However, when restricted to $(0,1)$ or $[0,1]$
		the function $x \mapsto x^2$ becomes uniformly continuous.
		(For $\eps > 0$ one can now pick for example $\delta = \min\{1,\eps\}/3$.)

		\ii The function $(0,1) \to \RR$ by $x \mapsto 1/x$ is \emph{not}
		uniformly continuous (same reason as before).
	\end{enumerate}
\end{example}

Now, as promised:
\begin{proposition}[Continuous on compact $\implies$ uniformly continuous]
	If $M$ is compact and $f \colon M \to N$ is continuous,
	then $f$ is uniformly continuous.
\end{proposition}
\begin{proof}[Proof using sequences]
	Fix $\eps > 0$, and assume for contradiction that for every $\delta = 1/k$
	there exists points $x_k$ and $y_k$ within $\delta$ of each
	other but with images $\eps > 0$ apart.
	By compactness, take a convergent subsequence $x_{i_k} \to p$.
	Then $y_{i_k} \to p$ as well, since the $x_k$'s and $y_k$'s are close to each other.
	So both sequences $f(x_{i_k})$ and $f(y_{i_k})$ should converge to $f(p)$ by sequential continuity,
	but this can't be true since the two sequences are always $\eps$ apart.
\end{proof}

\section{(Optional) Equivalence of formulations of compactness}
We will prove that:
\begin{theorem}
	[Heine-Borel for general metric spaces]
	For a metric space $M$, the following are equivalent:
	\begin{enumerate}[(i)]
		\ii Every sequence has a convergent subsequence,
		\ii The space $M$ is complete and totally bounded, and
		\ii Every open cover has a finite subcover.
	\end{enumerate}
\end{theorem}
We leave the proof that (i) $\iff$ (ii) as \Cref{thm:bzw};
the idea of the proof is much in the spirit of \Cref{thm:interval_compact}.
\begin{proof}
	[Proof that (i) and (ii) $\implies$ (iii)]
	We prove the following lemma, which is interesting in its own right.
	\begin{lemma}
		[Lebesgue number lemma]
		Let $M$ be a compact metric space and $\{U_\alpha\}$ an open cover.
		Then there exists a real number $\delta > 0$,
		called a \vocab{Lebesgue number} for that covering,
		such that the $\delta$-neighborhood of any point
		$p$ lies entirely in some $U_\alpha$.
	\end{lemma}
	\begin{subproof}[Proof of lemma]
		Assume for contradiction that for every $\delta = 1/k$
		there is a point $x_k \in M$
		such that its $1/k$-neighborhood isn't contained in any $U_\alpha$.
		In this way we construct a sequence $x_1$, $x_2$, \dots;
		thus we're allowed to take a subsequence which converges to some $x$.
		Then for every $\eps > 0$ we can find an integer $n$ such that $d(x_n, x) + 1/n < \eps$;
		thus the $\eps$-neighborhood at $x$ isn't contained in any $U_\alpha$ for every $\eps > 0$.
		This is impossible, because we assumed $x$ was covered by some open set.
	\end{subproof}
	Now, take a Lebesgue number $\delta$ for the covering.
	Since $M$ is totally bounded, finitely many $\delta$-neighborhoods cover the space,
	so finitely many $U_\alpha$ do as well.
\end{proof}

\begin{proof}
	[Proof that (iii) $\implies$ (ii)]
	One step is immediate:
	\begin{ques}
		Show that the covering condition $\implies$ totally bounded.
	\end{ques}
	The tricky part is showing $M$ is complete.
	Assume for contradiction it isn't and thus that the sequence $(x_k)$ is Cauchy,
	but it doesn't converge to any particular point.
	\begin{ques}
		Show that this implies for each $p \in M$, there is an $\eps_p$-neighborhood $U_p$
		which contains at most finitely many of the points of the sequence $(x_k)$.
		(You will have to use the fact that $x_k \not\to p$ and $(x_k)$ is Cauchy.)
	\end{ques}
	Now if we consider $M = \bigcup_p U_p$ we get a
	finite subcover of these open neighborhoods;
	but this finite subcover can only cover finitely
	many points of the sequence, by contradiction.
\end{proof}


\section{\problemhead}
The later problems are pretty hard;
some have the flavor of IMO 3/6-style constructions.
It's important to draw lots of pictures so one can tell what's happening.
% I'd be happy to learn of any easier ones.
Of these \Cref{thm:bzw} is definitely my favorite.

\begin{problem}
	Show that the closed interval $[0,1]$ and
	open interval $(0,1)$ are not homeomorphic.
	\begin{hint}
		$[0,1]$ is compact.
	\end{hint}
	\begin{sol}
		Compactness is preserved under homeomorphism,
		but $[0,1]$ is compact while $(0,1)$ is not.
	\end{sol}
\end{problem}

\begin{problem}
	Let $X$ be a topological space with the discrete topology.
	Under what conditions is $X$ compact?
	\begin{hint}
		If and only if it is finite.
	\end{hint}
\end{problem}

\begin{problem}
	[The cofinite topology is quasicompact only]
	We let $X$ be an infinite set and equip it with the
	\vocab{cofinite topology}:
	the open sets are the empty set and complements of finite sets.
	This makes $X$ into a topological space.
	Show that $X$ is quasicompact but not Hausdorff.
\end{problem}

\begin{problem}
	[Cantor's intersection theorem]
	\label{prob:cantor_intersect}
	Let $X$ be a compact topological space, and suppose
	\[ X = K_0 \supseteq K_1 \supseteq K_2 \supseteq \dots \]
	is an infinite sequence of nested nonempty closed subsets.
	Show that $\bigcap_{n \ge 0} K_n \neq \varnothing$.
\end{problem}

%\begin{sproblem}[Compact Implies Bounded]
%	Let $f \colon X \to \RR$ be a continuous function,
%	where $X$ is a compact topological space.
%	Show that $f$ is bounded.
%	\begin{hint}
%		Immediate by the fact that the image of $f$ is compact,
%		and hence bounded.
%		Remember this!
%	\end{hint}
%\end{sproblem}

\begin{problem}
	[Tychonoff's theorem]
	Let $X$ and $Y$ be compact metric spaces. Show that $X \times Y$ is compact.
	(This is also true for general topological spaces,
	but the proof is surprisingly hard,
	and we haven't even defined $X \times Y$ in general yet.)
	\label{prob:tychonoff}
	\begin{hint}
	Suppose $p_i = (x_i, y_i)$ is a sequence in $X \times Y$ ($i=1,2,\dots$).
	Take a sub-sequence such that the $x$-coordinate converges
	(throwing out some terms).
	Then take a sub-sequence of \emph{that} sub-sequence
	such that $y$-coordinate converges (throwing out more terms).
	\end{hint}
	\begin{sol}
	Suppose $p_i = (x_i, y_i)$ is a sequence in $X \times Y$ ($i=1,2,\dots$).
	Looking on the $X$ side, some subsequence converges:
	for the sake of illustration say it's $x_1, x_4, x_9, x_{16}, \dots \to x$.
	Then look at the corresponding sequence $y_1, y_4, y_9, y_{16}, \dots$.
	Using compactness of $Y$, it has a convergent subsequence, say
	$y_1, y_{16}, y_{81}, y_{256}, \dots \to y$.
	Then $p_1, p_{16}, p_{81}, \dots$ will converge to $(x,y)$.

	One common mistake is to just conclude
	that $(x_n)$ has a convergent subsequence
	and that $(y_n)$ does too.
	But these sequences could be totally unrelated.
	For this proof to work,
	you do need to apply compactness of $X$ first,
	and then compactness of $Y$ on the resulting \emph{filtered}
	sequence like we did here.
	\end{sol}
\end{problem}

\begin{dproblem}
	[Bolzano-Weierstra\ss\ theorem for general metric spaces]
	\onechili
	Prove that a metric space $M$ is sequentially compact
	if and only if it is complete and totally bounded.
	\label{thm:bzw}
	\begin{hint}
		Mimic the proof of \Cref{thm:interval_compact}.
		The totally bounded condition lets you do Pigeonhole.
	\end{hint}
\end{dproblem}

\begin{problem}
	[Almost Arzel\`a-Ascoli theorem]
	\onechili
	Let
	$f_1, f_2, \ldots \colon [0,1] \to [-100,100]$
	be an \vocab{equicontinuous} sequence of functions, meaning
	\[
		\forall \eps > 0 \quad
		\exists \delta > 0 \quad
		\forall n \;
		\forall x,y \quad
		\left( \left\lvert x-y \right\rvert <\delta
		\implies \left\lvert f_n(x) - f_n(y) \right\rvert < \eps \right)
	\]
	Show that we can extract a subsequence $f_{i_1}, f_{i_2}, \dots$
	of these functions such that for every $x \in [0,1]$,
	the sequence $f_{i_1}(x)$, $f_{i_2}(x)$, \dots\ converges.
\end{problem}

\begin{problem}
	\onechili
	Let $M = (M,d)$ be a bounded metric space.
	Suppose that whenever $d'$ is another metric on $M$
	for which $(M,d)$ and $(M,d')$ are homeomorphic
	(i.e.\ have the same open sets), then $d'$ is also bounded.
	Prove that $M$ is compact.
	\begin{hint}
		Assuming $M$ is not compact, construct an
		unbounded continuous function $F \colon M \to \RR$.
		Once such a function $F$ is defined, the metric
		\[ d'(x, y) \coloneqq d(x, y) + \abs{F(x) - F(y)} \]
		will establish the contrapositive of the problem.
	\end{hint}

	\begin{sol}
		The following solution is due to Royce Yao.
		We show the contrapositive:
		if $M$ is not compact, then there exists a homeomorphic unbounded metric.

		The main step is to construction
		an unbounded continuous function $F \colon M \to \RR$.
		Once such a function $F$ is defined, the metric
		\[ d'(x, y) \coloneqq d(x, y) + \abs{F(x) - F(y)} \]
		will solve the problem.

		So, let $a_1$, $a_2$, \dots\ be a sequence in $M$
		with no convergent subsequence.
		For each $a_i$, there exists a radius $r_i$ such that
		\[ 0 < r_i < \frac{1}{2} \min_{j} d(a_i, a_j) \]
		Define $C_i$ as an open ball at $a_i$ with radius $r_i$.
		Note that every ball is disjoint.
		Then, we define $F$ as follow
		\[
			F(x) = \begin{cases}
				0 & x \not\in C_i \\
				\frac{i}{r_1}(r_i - d(x, a_i)) & x \in C_i
			\end{cases}
		\]
		which can be seen to be continuous.
		Then, $F$ is unbounded by considering $F(a_i)$ as $i$ goes to infinity.
	\end{sol}
\end{problem}

\begin{problem}
	\twochili
	In this problem a ``circle''
	refers to the boundary of a disk with \emph{nonzero} radius.
	\begin{enumerate}[(a)]
		\ii Is it possible to partition the plane $\RR^2$
		into disjoint circles?
		\ii From the plane $\RR^2$ we delete two distinct points $p$ and $q$.
		Is it possible to partition the remaining points into disjoint circles?
	\end{enumerate}
	\begin{hint}
		The answer to both parts is no.

		For (a) use \Cref{prob:cantor_intersect}.

		For (b), color each circle in the partition
		based on whether it contains $p$ but not $q$,
		$q$ but not $p$, or both.
	\end{hint}
	\begin{sol}
		Part (a) follows by the Cantor intersection theorem
		(\Cref{prob:cantor_intersect}).
		Assume for contradiction such a partition existed.
		Take any of the circles $C_0$, and let $K_0$ denote the closed disk
		with boundary $C_0$.
		Now take the circle $C_1$ passing through the center of $C_0$,
		and let $K_1$ denote the closed disk with boundary $C_1$.
		If we repeat in this way,
		we get a nested sequence $K_0 \supseteq K_1 \supseteq \dots$
		and the radii of $C_i$ approach zero
		(since each is at most half the previous once).
		Thus some point $p$ lies in $\bigcap_n K_n$ which is impossible.

		Now for part (b),
		again assume for contradiction a partition into circles exists.
		Color a circle magenta if it contains $p$ but not $q$
		and color a circle cyan if it contains $q$ but not $p$.
		Color $p$ itself magenta and $q$ itself cyan as well.
		Finally, color a circle neon yellow if it contains both $p$ and $q$.
		(When we refer to coloring a circle,
		we mean to color all the points on it.)

		By repeating the argument in (a) there are no circles
		enclosing neither $p$ nor $q$.
		Hence every point is either magenta, cyan, or neon yellow.
		Now note that given any magenta circle,
		its interior is completely magenta.
		Actually, the magenta circles can be totally ordered
		by inclusion (since they can't intersect).
		So we consider two cases:
		\begin{itemize}
		 \ii If there is a magenta circle which is maximal by inclusion
		 (i.e.\ a magenta circle not contained in any other magenta circle)
		 then the set of all magenta points is just a closed disk.
		 \ii If there is no such magenta circle,
		 then the set of magenta points can also be expressed
		 as the union over all magenta circles of their interiors.
		 This is a union of open sets, so it is itself open.
		 \end{itemize}

		We conclude the set of magenta points is
		either a closed disk or an open set.
		Similarly for the set of cyan points.
		Moreover, the set of such points is convex.

		To finish the problem:
		\begin{itemize}
		\ii Suppose there are no neon yellow points.
		If the magenta points form a closed disk,
		then the cyan points are $\mathbb R^2$ minus a disk which is not convex.
		Contradiction. So the magenta points must be open.
		Similarly the cyan points must be open.
		But $\mathbb R^2$ is connected,
		so it can't be written as the union of two open sets.
		\ii Now suppose there are neon yellow points.
		We claim there is a neon yellow circle minimal by inclusion.
		If not, then repeat the argument of (a) to get a contradiction,
		since any neon yellow circle must have diameter the distance from $p$ to $q$.
		So we can find a neon yellow circle $\mathscr C$ whose
		interior is all magenta and cyan.
		Now repeat the argument of the previous part,
		replacing $\mathbb R^2$ by the interior of $\mathscr C$.
		 \end{itemize}
	\end{sol}
\end{problem}
